package com.atguigu.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {

        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "林冲", "豹子头");
        HeroNode heroNode3 = new HeroNode(3,"李逵","黑旋风");
        //HeroNode heroNode4 = new HeroNode(4,"浪里白条","张顺");

        HeroNode heroNode5 = new HeroNode(5,"李白","诗仙");
        HeroNode heroNode6 = new HeroNode(6,"杜甫","诗圣");
        HeroNode heroNode7 = new HeroNode(7,"白居易","诗哥");
        HeroNode heroNode8 = new HeroNode(8,"XXX","XXX");

        //普通添加方法
/*      list.add(heroNode1);
        list.add(heroNode2);
        list.add(heroNode3);
        list.add(heroNode4);*/

        //测试有序排名英雄的方法
        SingleLinkedList list = new SingleLinkedList();
        list.addByOrder(heroNode1);
        list.addByOrder(heroNode3);
        list.addByOrder(heroNode2);

        list.show();


       /*========= 测试从尾到头打印链表==========*/
           //reversPrint(list.getHead());

        /*=======测试单链表反转的方法============*/
          // reverseList(list.getHead());

        //测试查找单链表中倒数第k个节点
/*        HeroNode lastIndexNode = findLastIndexNode(list.getHead(), 1);
        System.out.println("倒数第K个节点是:" + lastIndexNode);
        list.show();*/

/*        //测试修改节点的方法
        HeroNode heroNode5 = new HeroNode(2,"卢俊义","小卢");
        list.update(heroNode5);

        //测试删除节点的方法
        //list.delete(4);

        list.show();

        //测试有效节点个数方法
        System.out.println(getLength(list.getHead()));

        //查找单链表中倒数第k个节点
        System.out.println(findLastIndexNode(list.getHead(),1));*/

    }

    /**
     * 统计链表中有效结点个数（不统计头结点）
     *
     * @param head 头结点
     * @return 结点有效个数
     */
    public static int getLength(HeroNode head) {

        if (head.next == null) {
            return 0;
        }

        int length = 0;
        //这里不统计头节点
        HeroNode temp = head.next;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        return length;
    }

    /**
     * 查找单链表中倒数第k个节点
     *
     * @param head  头节点
     * @param index 指定第几个节点
     * @return 查找到的节点
     * <p>
     * 思路
     * 1. 编写一个方法，接收head节点，同时接收一个index
     * 2. index 表示是倒数第index个节点
     * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
     * 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
     * 5. 如果找到了，则返回该节点，否则返回 null
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {

        if (head.next == null) {
            return null;
        }

        //第一次遍历得到链表的长度(有效个数)
        int size = getLength(head);
        //第二次遍历  size-index 位置，就是我们倒数的第K个节点
        //先做一个index的校验
        if (index <= 0 || index > size) {
            return null;
        }

        //定义给辅助变量， for 循环定位到倒数的index
        HeroNode cur = head.next;
        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }

        return cur;
    }

    /**
     * 单链表反转
     */
    public static void reverseList(HeroNode head) {
        //如果当前链表为空,或者只有一个节点,无需反转,直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }

        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reversHead = new HeroNode(0, "", "");
        while (cur != null) {
            next = cur.next;

            cur.next = reversHead.next;
            reversHead.next = cur;
            cur = next;
        }

        head.next = reversHead.next;
    }

    /**
     * 从尾到头打印单链表
     *
     * @param head
     */
    public static void reversPrint(HeroNode head) {

        //创建一个栈
        Stack<HeroNode> stack = new Stack<>();

        HeroNode temp = head.next;
        //将所有节点压入栈内
        while (temp != null) {
            //将当前节点加入到栈内
            stack.push(temp);
            //向后移
            temp = temp.next;
        }

        //遍历栈
        while (stack.size() > 0) {
            //出栈
            System.out.println(stack.pop());
        }
    }

    /*
    题目:合并两个有序的单链表,合并之后的链表依然有序

     */
    public static void mergeList(HeroNode head1,HeroNode head2) {

        //创建一个新的链表
        HeroNode hero3 = new HeroNode(0, "", "");


    }

}


//定义SingleLinkedList管理英雄
class SingleLinkedList{

    //先初始化一个头节点,头节点不能动,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    /*  添加节点单向链表
        当不考虑编号顺序时
        1.找到当前链表的最后节点
        2.将最后这个节点的next指向新节点
        */
    public void add(HeroNode heroNode){

        //head头节点不能动,因此我们需要一个辅助遍历 temp
        HeroNode temp = head;

        //遍历链表,找到最后
        while (true){
            if (temp.next == null){
                break;
            }

            //如果没有找到最后 将temp后移
            temp = temp.next;
        }

        //当退出while循环的时候,temp就指向了链表最后
        //将最后这个节点的next值指向新节点
        temp.next = heroNode;
    }

    //第二种方式在添加英雄的时候,根据排名将英雄插入到指定位置
    //如果有这个排名,则添加失败,并给出提示
    public void addByOrder(HeroNode heroNode){

        HeroNode temp = head;
        //因为单链表,因为我们找的temp是位于添加位置的前一个节点,否则插入不了
        //flag标志添加的编号是否存在,默认为false
        boolean flag = false;
        while (true){

            //说明temp已经在链表的最后
            if (temp.next == null) {
                break;
            }

            //位置找到,就在temp的后面插入
            if (temp.next.no > heroNode.no){
                break;
                //说明希望添加的heroNode编号已然存在
            }else if (temp.next.no == heroNode.no){
                flag = true;//编号存在
                break;
            }

            //后移 遍历当前链表
            temp = temp.next;
        }


        //判断flag的值
        //不能添加,编号已经存在
        if (flag){
            System.out.printf("准备插入的英雄的编号 %d已经存在, 不能加入\n",heroNode.no);
        }else {
            //插入到链表中,temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    //根据编号修改节点,编号不可修改
    public void update(HeroNode heroNode){

        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空~~~");
            return;
        }

        HeroNode temp = head.next;
        boolean flag = false;
        while (true){

            //已经遍历完链表
            if (temp == null){
                break;
            }

            if (temp.no == heroNode.no){
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }

        //根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        }else {//没找到
            System.out.printf("没有找到 编号 %d的节点,不能修改\n",heroNode.no);
        }
    }

    /*
    删除节点
    思路
    1.head头节点不能动,因此我们需要一个temp辅助节点找到待删除节点的上一个节点
    2.说明我们在比较的时候,是temp.next.no和需要删除的节点的no进行比较
     */
    public void delete(int no){
        HeroNode temp = head;
        boolean flag = false;
        while (true){

            if (temp.next == null){
                break;
            }

            if (temp.next.no == no){
                flag = true;
                break;
            }

            temp = temp.next;
        }

        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的 %d节点不存在 \n",no);
        }
    }

    public void show(){
        //判断链表是否为空
        if (head.next == null){
        System.out.println("链表为空~~~");
            return;
        }

        HeroNode temp = head.next;

        while (true){
            //判断是否到了链表最后
            if (temp == null){
                break;
            }

            System.out.println(temp);

            //将temp后移,一定小心
            temp = temp.next;
        }
    }
}

//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }
}